1. Field of the Invention
The present invention relates to an allocation apparatus and method for determining cell allocation in the automatic layout, etc. of semiconductor circuits.
2. Description of the Related Art
As the technology for semiconductor integrated circuits has recently improved, the improvement in integration of very large-scale integration (VLSI) chips and the increase in the scale of circuits has become remarkable. Since both the improvement in integration and the increase in circuit scale are accompanied by an increase in the number of cells included in VLSI chips, it is getting harder and harder to get an optimum solution to a cell allocation issue.
In the layout design of LSIs, the process of partitioning an allocation area on a chip is repeated utilizing a computer system, and thereby the default allocation of each cell is determined. The allocated cells correspond to module components, etc., the shapes of the cells are usually rectangular, and the cells have a certain area. As one conventional partitioning method there is a method of using a resistive network model based on the analogy of electric circuits (R-S. Tsay, E. Kuh, and C-P. Hsu, "A Sea-of-Gates Placement Algorithm", IEEE Design & Test of Computers, December 1988, pp.44-56).
FIG. 1A is a flowchart showing a block Gauss-Seidel method being one partitioning method using the resistive network model. When the process is started, first the system constructs a resistive network based on a net list for indicating the wiring of a given circuit (step S1).
Here, a resistive network means a graph in which cells are represented by nodes and a plurality of cells belonging to the same net are connected by means of edges. In this case, for the model indicating the connection of cells, a complete connection model as shown in FIG. 1B is used. In the complete connection model each node on one net is connected with all other nodes of the net.
Then, the simultaneous linear equations of the constructed resistive network are created, and are solved using a successive over-relaxation (SOR) method (step S2). The SOR method corresponds to a generalized Gauss-Seidel method, which is an iterative method for solving simultaneous linear equations.
It is generally known that the solution of the simultaneous linear equations of a resistive network gives the cell positions where the following objective function of a cell allocation issue becomes a minimum. ##EQU1##
where n, (x.sub.i, y.sub.i), and x and y represents the total number of cells, the coordinates of the i-th cell (i=1, 2, 3, . . . , n), and the n-dimensional vector with the x-coordinate and y-coordinate of n cells as the elements, respectively.
c.sub.ij is a connection coefficient between the i-th cell and j-th cell, where c.sub.ii =0 and c.sub.ij =c.sub.ji. The matrix B of n.times.n is expressed using a symmetrical matrix C with a c.sub.ij as the element as follows: EQU B=D-C (2)
Provided that a matrix D is a diagonal matrix with the following diagonal element. ##EQU2##
Therefore, the objective function L (x, y) of the equation (1) corresponds to the sum of squares of the wire lengths between the cells, and it is considered that the cell position (x, y) where the value of L (x, y) becomes a minimum, gives the optimum cell allocation. The solution of the simultaneous linear equations of a resistive network corresponds to a cell position such as this.
Then, the obtained cell position (x.sub.i, y.sub.i) is sorted according to the respective values of the x-coordinate and y-coordinate (step S3). Then, cells are put in one partitioned block of the allocated area in ascending order of the respective coordinate values, and when the cell areas are balanced, the remaining cells are put in the other partitioned block (step S4).
The point where the cell areas are balanced means, for example, the point where the total sum of cell areas contained in a block becomes about half of the sum of all cell areas. In this way, n cells are so divided into two blocks that both areas are balanced, and then the process is terminated. By repeating the division of both the x-direction and y-direction in this way, the size of the blocks is gradually reduced, and finally each block can be made to contain only one cell.
However, the above-mentioned conventional partitioning method has the following problems.
Since a complete connection model as shown in FIG. 1B is used when converting a net list to a resistive network, the value of the objective function does not become small unless all distances between the cells connected to a certain net are about the same. Accordingly, as a result, cells are uniformly distributed in two-dimensions, and the result does not necessarily match with an actual wiring pattern.
In this partitioning method, although the solution is sorted according to the value of a cell position coordinate when applying a block Gauss-Seidel method, the number of cuts on the boundary of blocks is not taken into consideration. The number of cuts means the number of wires transversing a cut line (border line), and in the layout design of semiconductor integrated circuits, it is desirable to minimize this number.